The present invention relates to a method for managing tasks in a computer system. Furthermore, the invention relates to a computer system configured for a method for managing tasks in a computer system.
Customers expect performance improvements for every new computer model. In the past, advances in solid state physics allowed increasing clock frequency from about 1 MHz around 1980 to several GHz today. However, currently, improvements of solid state physics become more difficult. Increased speed of program execution may thus come from improved CPU structure.
Normally, the machine instructions of a binary computer program are executed one after each other. The instructions are fetched and pipelined by an instruction fetch unit and executed by an execution unit. Branch instructions may interrupt the sequential execution and redirect program execution to somewhere else. Branch instructions are used to implement high-level program constructs as well as all kinds of loops. On some CPUs branch instructions are also used to implement subprogram calls. Several systems provide instructions tailored towards the implementation of counting loops. These branch instructions form a loop and consider a given counter as loop counter, increment or decrement this counter, and branch depending on whether the new counter value reached a reference value.
The overlapping, pipelined execution of instruction as used by many processors complicates the execution of branch statements. The address of the next instruction to execute is only known after the branch instruction has completed. However, at the point where the execution of a branch instruction is complete, the instruction fetch unit has already begun to fetch and pipeline instructions following the branch instruction. Depending if the branch is taken or not, the pipeline needs to execute different instructions, starting at the target address of the branch. This, however, requires a new pipeline start at the target address, thus delaying program execution.
It is therefore state of the art that processors comprise a branch prediction unit for doing some kind of branch prediction, based on recorded information about some branch instruction's behavior in the past. Common to all approaches for branch prediction is the need to store information about the past behavior of the instructions to be executed. The processor provides memory for this purpose, in the following called branch prediction history table.
When the execution of a program starts, branch prediction first needs to learn about the branches used in the code. Information stored usually includes the branch instruction's address or some hash value derived from this address, whether the branch was taken or not, what the branch instruction's target address was, and depending on the prediction algorithm also some additional information e.g. about the path leading to the branch instruction.
Branch prediction does not only need to learn when the user starts a new application program but also whenever the operating system performs a context switch by assigning the physical processor to a different operating-system-level process, or when the hypervisor assigns the physical processor to a different virtual machine. The branch prediction unit typically has a fixed amount of memory for the branch prediction history table within the processor to store information. The branch prediction unit fills the memory as the execution of the current binary proceeds. After a switch to another task, the memory is filled with information belonging to the previous binary which does not lead to correctly predicted branches in the new task. Thus, the branch prediction unit starts to relearn the branches of the task after a task switch, implying that the rate of mispredicted branches will be high which reduces execution speed.
Therefore, when a task switch is performed, the branch prediction history table of the currently executed task is saved into a task structure of this task. If a task is to be continued or started, the processor can restore the data of this task, respectively the branch prediction history table of this task. However, the size of the branch prediction history table may become very large. The saving process may reduce the performance of the processor.